#include <stdio.h>
#include <stdlib.h>

#define MAX_NODES 20000000
#define put_node(st) _queue[_tl++] = st
#define get_node() _queue[_hd++]
#define queue_not_empty (_hd < _tl)
#define NUM_STONES 7
#define MAX_STEPS NUM_STONES*1000

/**********    全局变量定义区开始    **********/
typedef struct state_t{
	/*状态的定义*/
	int stones[NUM_STONES]; //对应位置为1，表示绿青蛙；为-1，表示棕青蛙；为0，表示没有青蛙。	
	int parent_pos; // 父节点位置；若为-1，表示没有父节点 
}state_t;


state_t _queue[MAX_NODES];//状态队列

int _hd = 0, _tl = 0;//队列的头、尾位置；_tl - _hd 即为队列中元素的数量

/**********    全局变量定义区结束    **********/


/**********    辅助函数定义区开始    **********/

/*打印一个状态*/
void print_state(state_t st){
	int i;
	for (i=0;i<NUM_STONES;i++){
		printf("%d ", st.stones[i]);
	}
	printf("\n");
}
 
/*从输入的参数 st开始，不断追溯父节点直到初始节点，并输出以st结束的移动路径*/
void print_result(state_t st){

}

/*检查队列中是否存在重复状态*/
//从_queue[0] 开始 到  _queue[_tl] 逐一检查  
// 返回 1: 存在重复
// 返回其他： 不存在重复
int state_exists(state_t st){
	return 1;
}

/*在队列中增加一个子节点，op 为空闲位置的移动方式, par_pos是父节点在队列中位置*/
//op 的取值 1, 2, -1, -2， 表示空闲位置的移动方向和幅度 。
//比如 op=1，表示空闲位置向右移动 1 位，等同于 在空闲位置右侧的青蛙跳到空闲位置 
void append_child(state_t parent, int op, int par_pos){	
}

/*生成最初的状态*/
void init(state_t *st){
}

/*
判断一个状态是否为最终状态；
返回值：
 1： 输入状态为最终状态
 其他： 输入状态不是最终状态 
*/ 
int is_target(state_t st){
	return 1;
}




/**********    辅助函数定义区结束    **********/

/**********    主要函数定义区开始    **********/

/*从初始状态出发，采用广度优先，搜索目标状态*/
void cross_river(state_t init_st){
	put_node(init_st);
 
	while(queue_not_empty){
		state_t st = get_node();
		
 		if (is_target(st) == 1){ 
			print_result(st);
			break;
        }

		/*从一个状态出发，生成新的状态，并且存入到队列中*/		
		//最多四个子状态： 空闲位置“0” 左移（右移）一位或两位		
		//注意：在加入新的节点之前，须扫描队列，确保不引入重复节点 				
	} 	 
}

int main(){
	state_t st;
	init ( &st ); 
	
	cross_river(st);
	return 1;
}

/**********    主要函数定义区结束    **********/

